// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

func topKFreq(array []int, n int) []int {
	var res []int

	frequencyMap := make(map[int]int)

	for i := 0; i < len(array); i++ {
		frequencyMap[array[i]]++
	}

	var minHeap [][2]int

	for key, val := range frequencyMap {
		add(&minHeap, [2]int{key, val})

		if len(minHeap) > n {
			pop(&minHeap)
		}
	}

	for i := 0; i < len(minHeap); i++ {
		res = append(res, minHeap[i][0])
	}

	return res
}

func add(heap *[][2]int, item [2]int) {
	if heap == nil {
		panic("nil pointer")
	}

	if len(*heap) == 0 {
		*heap = append(*heap, item)
		return
	}

	*heap = append(*heap, item)
	heapUp(*heap, len(*heap)-1)
}

func pop(heap *[][2]int) [2]int {
	if heap == nil {
		panic("nil pointer")
	}

	if len(*heap) == 0 {
		panic("empty heap")
	}

	poppedItem := (*heap)[0]

	lastIdx := len(*heap) - 1
	(*heap)[0], (*heap)[lastIdx] = (*heap)[lastIdx], (*heap)[0]
	*heap = (*heap)[:lastIdx]
	heapDown(*heap, 0, 0, lastIdx-1)

	return poppedItem
}

func heapUp(array [][2]int, pos int) {
	parent := (pos - 1) / 2

	if parent >= 0 && array[pos][1] < array[parent][1] {
		array[pos], array[parent] = array[parent], array[pos]
		heapUp(array, parent)
	}
}

func heapDown(array [][2]int, pos int, low int, high int) {
	l := pos*2 + 1
	r := pos*2 + 2
	smaller := pos

	if low <= l && l <= high && array[l][1] < array[smaller][1] {
		smaller = l
	}

	if low <= r && r <= high && array[r][1] < array[smaller][1] {
		smaller = r
	}

	if smaller != pos {
		array[smaller], array[pos] = array[pos], array[smaller]
		heapDown(array, smaller, 0, high)
	}
}

func main() {
	array := []int{1, 1, 1, 2, 2, 3}
	n := 2
	res := topKFreq(array, n)
	fmt.Println(res)
}

//$ go run interview4-7.go
//[2 1]
